package cn.good.yan.sf.t5;

/**
 * 5 有序列表去重  --  1 1 1 4 5 ---  1 4 5
 *
 * @author shengren.yan
 * @create 2024-07-06
 */
public class DupNode {

    private int value;
    public DupNode next;

    public DupNode(int value, DupNode next) {
        this.value = value;
        this.next = next;
    }

    // 去重：方式1 (双指针)   1 1 1 4 5 ---  1 4 5
    public DupNode qc1(DupNode old) {
        if (old == null || old.next == null) {
            return old;
        }
        DupNode p1 = old;
        DupNode p2 = null;
        while ((p2 = p1.next) != null) {
            if (p1.value == p2.value) {
                p1.next = p2.next;
            } else {
                p1 = p1.next;
            }
        }
        return old;
    }

    // 去重：方式2 (递归)   1 1 1 4 5 ---  1 4 5
    public DupNode qc2(DupNode old) {
        if (old == null || old.next == null) {
            return old;
        }
        if (old.value == old.next.value) {
            return qc2(old.next);
        } else {
            old.next = qc2(old.next);
            return old;
        }
    }

    // 去重 重复的元素都要删除  1 1 1 4 5 ---  4 5
    public DupNode qcAll(DupNode old) {
        if (old == null || old.next == null) {
            return old;
        }
        DupNode head = new DupNode(-1, old);
        DupNode p1 = head;
        DupNode p2 = null;
        DupNode p3 = null;
        while ((p2 = p1.next) != null && (p3 = p2.next) != null) {
            if (p2.value == p3.value) {
                while ((p3 = p3.next) != null && p3.value == p2.value) {

                }
                p1.next = p3;
            } else {
                p1 = p1.next;
            }
        }
        return head.next;
    }

    // 去重 重复的元素都要删除  1 1 1 4 5 ---  4 5
    public DupNode qcAll2(DupNode old) {
        if (old == null || old.next == null) {
            return old;
        }
        if (old.value == old.next.value) {
            DupNode next = old.next.next;
            while (next != null && next.value == old.value) {
                next = next.next;
            }
            return qcAll2(next);

        } else {
            old.next = qcAll2(old.next);
            return old;
        }
    }

    public static void main(String[] args) {
        DupNode o5 = new DupNode(5, null);
        DupNode o4 = new DupNode(4, o5);
        DupNode o3 = new DupNode(1, o4);
        DupNode o2 = new DupNode(1, o3);
        DupNode o1 = new DupNode(1, o2);
        o1.loop();
        System.out.println("------------");
        // 方式1：
//        DupNode r1 = o1.sort(o1);
//        r1.loop();
        // 方式2：
//        DupNode r2 = o1.sort2(o1);
//        r2.loop();
        // 方式3 ：重复的元素都要删除
//        DupNode r3 = o1.qcAll(o1);
//        r3.loop();
        // 方式4 ：重复的元素都要删除
        DupNode r4 = o1.qcAll2(o1);
        r4.loop();


    }

    public void loop() {
        for (DupNode i = this; i != null; i = i.next) {
            System.out.println(i.value);
        }
    }

}
